package alo.p3.work;

import alo.p3.ListNode;

import java.util.Deque;
import java.util.LinkedList;

//两个链表的数相加，1-2-3-4  +  1-2-2  = 1-3-5-6
public class addTwoNumbers {
    //使用栈，难点在于进位
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Deque<Integer> stack1 = new LinkedList<Integer>();
            Deque<Integer> stack2 = new LinkedList<Integer>();
            while (l1 != null) {
                stack1.push(l1.getData());
                l1 = l1.getNext();
            }
            while (l2 != null) {
                stack2.push(l2.getData());
                l2 = l2.getNext();
            }
            int carry = 0;
            ListNode ans = null;
            while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
                int a = stack1.isEmpty() ? 0 : stack1.pop();
                int b = stack2.isEmpty() ? 0 : stack2.pop();
                int cur = a + b + carry;
                carry = cur / 10;
                cur %= 10;
                //新建一个链表
                ListNode curnode = new ListNode(cur);
                curnode.setNext(ans);
                ans = curnode;
            }
            /*
            while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
                int sum = carry;
                sum += stack1.isEmpty()? 0: stack1.pop();
                sum += stack2.isEmpty()? 0: stack2.pop();
                ListNode node = new ListNode(sum % 10);
                node.next = ans;
                ans = node;
                carry = sum / 10;
            }
            */
            return ans;
        }
    }
    //使用递归
    class Solution2{
        int flow=0;
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null) return l2;
            if(l2==null) return l1;
            ListNode res1=l1,res2=l2;
            int len1=0,len2=0;
            while(l1!=null){
                len1++;
                l1=l1.getNext();
            }
            while(l2!=null){
                len2++;
                l2=l2.getNext();
            }
            ListNode res=len1>len2?add(res1,res2,len1,len2):add(res2,res1,len2,len1);
            if(flow==1) {
                res1=new ListNode(1);
                res1.setNext(res);
                return res1;
            }
            return res;
        }
        public ListNode add(ListNode l1, ListNode l2,int len1,int len2) {
            int temp;
            if((len1==1)&&(len2==1)){
                temp=l1.getData();
                l1.setData((l1.getData()+l2.getData())%10);
                flow=(temp+l2.getData())/10;
                return l1;
            }
            if(len1>len2) {
                temp=l1.getData();
                l1.setNext(add(l1.getNext(), l2,len1-1,len2));
                l1.setData((temp+flow)%10);
                flow=(temp+flow)/10;
                return l1;
            }
            l1.setNext(add(l1.getNext(), l2.getNext(),len1-1,len2-1));
            temp=l1.getData();
            l1.setData((temp+flow+l2.getData())%10);
            flow=(temp+flow+l2.getData())/10;
            return l1;

        }
        
    }
}
